#!/usr/bin/python

import mathex

M = 10000000

def totient(n):
    ret = n
    for k in mathex.primeFactorOf(n):
        ret = ret/k * (k-1)
    return ret
def gen(bit):
    limit = int(pow(M, 1.0/bit))
    
    index = 0
    while mathex.primeList[index]<limit:
        index += 1
    while index >= 0:
        
def main():
##     for bit in range(2,7):
##         for pl in gen(bit):
            
    for n in xrange(10000000,2,-1):
        t = totient(n)
        tl = list(str(t))
        nl = list(str(n))
        tl.sort()
        nl.sort()
        if tl == nl:
            print n
            print t

if __name__ == '__main__':
    main()
    
